//-*-c++-*-
// Copyright (C) 2002-2008 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#ifndef __IRR_LINE_2D_H_INCLUDED__
#define __IRR_LINE_2D_H_INCLUDED__


#include "vector2d.h"
#include "circle2d.h"

#define ROUNDING_ERROR_32 0.000001f
//! 2D line between two points with intersection methods.
template <class T>
class line2d
{
public:
	//! Default constructor for line going from (0,0) to (1,1).
	line2d() : start(0,0), end(1,1) {}
	//! Constructor for line between the two points.
	line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {}
	//! Constructor for line between the two points given as vectors.
	line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {}
	//! Copy constructor.
	line2d(const line2d<T>& other) : start(other.start), end(other.end) {}

	// operators

	line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); }
	line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; }

	line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); }
	line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; }

	bool operator==(const line2d<T>& other) const
	{ return (start==other.start && end==other.end) || (end==other.start && start==other.end);}
	bool operator!=(const line2d<T>& other) const
	{ return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}

	// functions
	//! Set this line to new line going through the two points.
	void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);}
	//! Set this line to new line going through the two points.
	void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);}
	//! Set this line to new line given as parameter.
	void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);}

	//! Get length of line
	/** \return Length of the line. */
	double getLength() const { return start.getDistanceFrom(end); }

	//! Get squared length of the line
	/** \return Squared length of line. */
	T getLengthSQ() const { return start.getDistanceFromSQ(end); }

	//! Get middle of the line
	/** \return center of the line. */
	vector2d<T> getMiddle() const
	{
		return (start + end) * (T)0.5;
	}

	//! Get the normal vector of the line.
	/** \return The normal vector of the line. */
	vector2d<T> getNormal() const { return vector2d<T>( -(start.Y - end.Y),start.X - end.X); }

	//! Get the vector of the line.
	/** \return The vector of the line. */
	vector2d<T> getVector() const { return vector2d<T>(start.X - end.X, start.Y - end.Y); }

	//! Get the point relection in the line.
	/** \return The point relection in the line. */
	vector2d<T> getRelectionPoint(const vector2d<T>& p) const
	{
		T orient = this->getPointOrientation(p);
		if(orient == 0)
			return p;
		
		vector2d<T> closest = this->getClosestPoint(p,false);


		return p + 2*(closest - p);
		//return p - 2*(closest - p);

	}

	//! Get the line translate to point by R.
	/** \return The line translate to point by R. */
	bool getLineTransToPoint(const vector2d<T>& p, T R, line2d<T>& out) const
	{
		if(getPointOrientation(p) == 0)
			return false;
		vector2d<T> normal = this->getNormal();

		out.start = this->start + (normal.normalize() * R);
		out.end = this->end + (normal.normalize() * R);

		return true;
	}

	//! Tests if this line intersects with a circle.
	/** \return True if there is an intersection, false if not. */
	bool intersectWith(const circle2d<T>& circle, vector2d<T>& out1,vector2d<T>& out2) const
	{
		line2d<T> tline = this->operator -(circle.center);
		T dx = tline.end.X - tline.start.X;
		T dy = tline.end.Y - tline.start.Y;
		T dr = sqrt(dx * dx + dy * dy);
		T D = tline.start.X * tline.end.Y - tline.end.X * tline.start.Y;
		T dr2 = dr * dr;
		T delta = circle.radius *circle.radius  * dr2 - D * D;
		

		if(delta <=0)
			return false;
		T sqrdelta  =  sqrt(delta);

		T sgndy = 1;
		if(dy < 0)
			sgndy = -1;
		out1.X = (D * dy + sgndy * dx * sqrdelta)/dr2;
		out1.Y = (-D * dx + CMath::Abs(dy) * sqrdelta)/dr2;
		out1 += circle.center;

		out2.X = (D * dy - sgndy * dx * sqrdelta)/dr2;
		out2.Y = (-D * dx - CMath::Abs(dy) * sqrdelta)/dr2;
		out2 += circle.center;

		return true;
	}

	//! Tests if this line intersects with another line.
	/** \param l: Other line to test intersection with.
		\param out: If there is an intersection, the location of the
		intersection will be stored in this vector.
		\return True if there is an intersection, false if not. */
	bool intersectWith(const line2d<T>& l, vector2d<T>& out) const
	{
		vector2d<T> d0 = end - start;
		vector2d<T> d1 = l.start - l.end;

		// check "parallel" lines
		float det = d0.X * d1.Y - d0.Y * d1.X;
		if (det > -ROUNDING_ERROR_32 && det < ROUNDING_ERROR_32)
		{
			return false;
		}
		det = 1.0f / det;

		vector2d<T> d01 = l.start - start;

		// Check intersection with this line
		float t = (d01.X * d1.Y - d01.Y * d1.X) * det;

		out = start + (d0 * t);
		if (t < 0.0f || t > 1.0f)
		{
			return false;
		}

		// check intersection with other line
		t = (d0.X * d01.Y - d0.Y * d01.X) * det;
		if (t < 0.0f || t > 1.0f)
		{
			return false;
		}
        return true;
	}

	//! Get unit vector of the line.
	/** \return Unit vector of this line. */
	vector2d<T> getUnitVector() const
	{
		T len = (T)(1.0 / getLength());
		return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
	}

	//! Get angle between this line and given line.
	/** \param l Other line for test.
		\return Angle in degrees. */
	double getAngleWith(const line2d<T>& l) const
	{
		vector2d<T> vect = getVector();
		vector2d<T> vect2 = l.getVector();
		return vect.getAngleWith(vect2);
	}

	//! Tells us if the given point lies to the left, right, or on the line.
	/** \return 0 if the point is on the line
		<0 if to the left, or >0 if to the right. */
	T getPointOrientation(const vector2d<T>& point) const
	{
		return ( (end.X - start.X) * (point.Y - start.Y) -
				 (point.X - start.X) * (end.Y - start.Y) );
	}

	//! Check if the given point is a member of the line
	/** \return True if point is between start and end, else false. */
	bool isPointOnLine(const vector2d<T>& point) const
	{
		T d = getPointOrientation(point);
		return (d == 0 && point.isBetweenPoints(start, end));
	}

	//! Check if the given point is between start and end of the line.
	/** Assumes that the point is already somewhere on the line. */
	bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
	{
		return point.isBetweenPoints(start, end);
	}

	//! Get the closest point on this line to a point
	vector2d<T> getClosestPoint(const vector2d<T>& point,bool inner = true) const
	{
		vector2d<T> c = point - start;
		vector2d<T> v = end - start;
		T d = (T)v.getLength();
		v /= d;
		T t = v.dotProduct(c);

		if(inner)
		{
			if (t < (T)0.0) return start;
			if (t > d) return end;
		}

		v *= t;
		return start + v;
	}

	//! Start point of the line.
	vector2d<T> start;
	//! End point of the line.
	vector2d<T> end;
};

//! Typedef for an f32 line.
typedef line2d<float> line2df;
//! Typedef for an integer line.
typedef line2d<int> line2di;

#endif

